package cn.mayday.algorithms.year2021.month1.位运算;

import java.util.HashMap;
import java.util.Map;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
 * 输出: 2
 *
 * @author Mayday05
 * @date 2021/1/8 14:05
 */
public class Off039MajorityElement {

    //【位运算专题】
    public static void main(String[] args) {
        int[] test1 = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        int result1 = new Off039MajorityElement().majorityElement(test1);
        System.out.println("result1 ===" + result1);


    }


    // 方法一：哈希表统计法
    // 时间和空间复杂度都是O(n)
    public int majorityElement1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer temp : nums) {
            Integer value = map.get(temp);
            if (value == null) {
                value = 0;
                map.put(temp, value);
            } else {
                value++;
                map.put(temp, value);
            }

            if (value >= nums.length / 2) {
                return temp; // 如果找到直接返回
            }
        }
        return -1;
    }


    // 方法二： 数组排序，中位数, 时间复杂度至少为O(NlogN)


    // 方法三： 最佳解法 摩尔投票法，时间复杂度为O(N)，空间复杂度为O(1)
    // 特点：是和不是分别代表1和-1，这样票数统计为0时，即可重新开始假设，由于至少一半，因此最后剩下的
    public int majorityElement(int[] nums) {
        int vote = 0;
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            // 为0时，假设首个即为众位数
            if (vote == 0) {
                temp = nums[i];
                vote++;
            } else {
                if (temp == nums[i]) {
                    vote++;
                } else {
                    vote--;
                }
            }
        }
        return temp;
    }
}
